break; /* Höhe hat sich geändert, deswegen bleibt niedriger = TRUE! */
}
}
return(TRUE);
}
void ersatz_finden(Knoten **knoten, Knoten **zu_loeschen, int *niedriger) /* sucht den In-Order-Vorgänger und setzt ihn an die Stelle von *zu_loeschen */
{
Knoten *hilf;
hilf = *knoten;
if (hilf->rechts != NULL) /* rechter Sohn ist vorhanden? */
{
ersatz_finden(&hilf->rechts, zu_loeschen, niedriger); /* vom linken Sohn das rechteste Blatt suchen (rek.) */
if (*niedriger) /* Ist der Baum nun niedriger? */
niedriger_rechts(knoten, niedriger); /* rechts ist es niedriger geworden. Ausgleichen? */
}
else
{
knoten = &hilf->links; /* linken Teilbaum des alten Kindes ersetzen */
hilf->links = (*zu_loeschen)->links; /* linken Teilbaum an Ersatz hängen */
hilf->rechts = (*zu_loeschen)->rechts; /* rechten Teilbaum an Ersatz hängen */
zu_loeschen = &hilf; /* Generationswechsel. das alte Kind wird nun Vater */
*niedriger = TRUE;
}
}
/*
1. Ersatz finden und an Stelle übergeben
2. ersetztes Element löschen
3. Baum ausgleichen ab alter Ersatz-Stelle
*/
int loeschen(Knoten **wurzel, Knoten *eintrag, int *niedriger)
{
int rc, erg;
Knoten *hilf;
if (*wurzel == NULL) /* Eintrag nicht gefunden? */